package test;

import com.alibaba.fastjson2.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author sunzhuokun
 * @date 16:54 2024/5/14
 * @description 区间交集
 * 给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为
 * [3,5])。公共区间之间 若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。按升序排列 输出合并后的区间列表。
 * <p>
 * 输入描述: 一组区间列表，区间数为 N: 0<=N<=1000;区间元素为 X: -10000<=X<=10000。
 * 输出描述: 升序排列的合并区间列表
 * <p>
 * 备注:
 * 1、区间元素均为数字，不考虑字母、符号等异常输入。
 * 2、单个区间认定为无公共区间。
 * 示例:
 * 输入
 * [[0, 3], [1, 3], [3, 5], [3, 6]]
 * 输出
 * [[1, 5]]
 */
public class IntervalIntersection2_区间交集 {

    public static void main(String[] args) {
        // {0, 3}, {1, 3}, {3, 5}, {3, 6}
        // {1, 3}, {3, 5}
        int[][] intervals = new int[][]{{1, 3}, {3, 5}};
        System.out.println(JSON.toJSONString(commonSectionMerge(intervals)));
    }

    private static List<int[]> commonSectionMerge(int[][] intervals) {
        // 公共区间列表
        List<int[]> commonSection = new ArrayList<>();
        if (intervals.length == 1) {
            commonSection.add(intervals[0]);
            return commonSection;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // 两两对比取出所有交集列表
        for (int i = 0; i < intervals.length - 1; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                // 存在交集
                if (intervals[i][1] >= intervals[j][0]) {
                    commonSection.add(new int[]{intervals[j][0], Math.min(intervals[i][1], intervals[j][1])});
                }
            }
        }
        if (commonSection.size() == 1) {
            commonSection.add(commonSection.get(0));
            return commonSection;
        }

        commonSection.sort(Comparator.comparingInt(a -> a[0]));

        int l = commonSection.size();
        int i = 0;
        // 合并交集列表之间的公共区间
        while (i < l - 2) {
            if (commonSection.get(i)[1] >= commonSection.get(i + 1)[0]) {
                int[] arr = commonSection.get(i);
                arr[1] = Math.max(commonSection.get(i)[1], commonSection.get(i + 1)[1]);

                commonSection.remove(i + 1);
                l -= 1;
            } else {
                i += 1;
            }
        }

        return commonSection.stream().distinct().collect(Collectors.toList());
    }
}
